树剖||树链剖分||线段树||BZOJ4034||Luogu3178||[HAOI2015]树上操作

1 #include
2 #include
3 #include
4 #define ll long long
5 #define max(a,b) ((a)>(b)?(a):(b))
6 using namespace std;
7 inline ll rd(){
8 ll x&＃61;0,f&＃61;1;char c&＃61;getchar();
9 while(c<&＃39;0&＃39;||c>&＃39;9&＃39;){if(c&＃61;&＃61;&＃39;-&＃39;)f&＃61;-1; c&＃61;getchar();}
10 while(c>&＃61;&＃39;0&＃39;&&c<&＃61;&＃39;9&＃39;){x&＃61;x*10&＃43;c-&＃39;0&＃39;; c&＃61;getchar();}
11 return f*x;
12 }
13 const ll maxn&＃61;100005,maxq&＃61;100005;
14 ll N,Q,num_edge&＃61;0,edge_head[maxn],W[maxn],a,b,seg[maxn],rev[maxn],fa[maxn];
15 ll top[maxn],son[maxn],size[maxn],tu[maxn],X,A,Ans,o;
16 struct Edge{
17 int to,nx;
18 }edge[maxn<<1];
19 inline void Add_edge(int from,int to){
20 edge[&＃43;&＃43;num_edge].nx&＃61;edge_head[from];
21 edge[num_edge].to&＃61;to;
22 edge_head[from]&＃61;num_edge;
23 return;
24 }
25 inline void Dfs1(int x,int f){
26 fa[x]&＃61;f;
27 size[x]&＃61;1;
28 for(int i&＃61;edge_head[x];i;i&＃61;edge[i].nx){
29 int y&＃61;edge[i].to;
30 if(y!&＃61;f){
31 Dfs1(y,x);
32 size[x]&＃43;&＃61;size[y];
33 if(size[y]>size[son[x]])son[x]&＃61;y;
34 }
35 }
36 return;
37 }
38 inline void Dfs2(int x){
39 tu[x]&＃61;seg[0];
40 if(son[x]){
41 int y&＃61;son[x];
42 seg[y]&＃61;&＃43;&＃43;seg[0];//seg[x]:x在线段树中的下标
43 rev[seg[0]]&＃61;y;
44 top[y]&＃61;top[x];
45 Dfs2(y);
46 tu[x]&＃61;max(tu[x],tu[y]);
47 }
48 for(int i&＃61;edge_head[x];i;i&＃61;edge[i].nx){
49 int y&＃61;edge[i].to;
50 if(top[y]&＃61;&＃61;0){
51 seg[y]&＃61;&＃43;&＃43;seg[0];
52 rev[seg[0]]&＃61;y;
53 top[y]&＃61;y;
54 Dfs2(y);
55 tu[x]&＃61;max(tu[x],tu[y]);
56 }
57 }
58 return;
59 }
60 struct Tree{
61 ll sum,l,r,flag;
62 }t[maxn<<3];
63 inline void Build(int k,int l,int r){
64 t[k].l&＃61;l;t[k].r&＃61;r;
65 if(l&＃61;&＃61;r){
66 t[k].sum&＃61;W[rev[l]];
67 return;
68 }
69 int mid&＃61;(l&＃43;r)>>1,ls&＃61;k<<1,rs&＃61;k<<1|1;
70 Build(ls,l,mid);Build(rs,mid&＃43;1,r);
71 t[k].sum&＃61;t[ls].sum&＃43;t[rs].sum;
72 return;
73 }
74 inline void Pushdown(int k){
75 if(t[k].flag){
76 int ls&＃61;k<<1,rs&＃61;k<<1|1,ln&＃61;t[ls].r-t[ls].l&＃43;1,rn&＃61;t[rs].r-t[rs].l&＃43;1;
77 t[ls].sum&＃43;&＃61;t[k].flag*ln;t[rs].sum&＃43;&＃61;t[k].flag*rn;
78 t[ls].flag&＃43;&＃61;t[k].flag;t[rs].flag&＃43;&＃61;t[k].flag;
79 t[k].flag&＃61;0;
80 }
81 return;
82 }
83 inline void Update(int k,int ql,int qr,ll s){
84 int l&＃61;t[k].l,r&＃61;t[k].r;
85 if(ql<&＃61;l&&r<&＃61;qr){
86 t[k].sum&＃43;&＃61;s*(r-l&＃43;1);
87 t[k].flag&＃43;&＃61;s;
88 return;
89 }
90 Pushdown(k);
91 int mid&＃61;(l&＃43;r)>>1,ls&＃61;k<<1,rs&＃61;k<<1|1;
92 if(ql<&＃61;mid)Update(ls,ql,qr,s);
93 if(qr>mid)Update(rs,ql,qr,s);
94 t[k].sum&＃61;t[ls].sum&＃43;t[rs].sum;
95 return;
96 }
97 inline void Query(int k,int ql,int qr){
98 int l&＃61;t[k].l,r&＃61;t[k].r;
99 if(ql<&＃61;l&&r<&＃61;qr){
100 Ans&＃43;&＃61;t[k].sum;
101 return;
102 }
103 Pushdown(k);
104 int mid&＃61;(l&＃43;r)>>1,ls&＃61;k<<1,rs&＃61;k<<1|1;
105 if(ql<&＃61;mid)Query(ls,ql,qr);
106 if(qr>mid)Query(rs,ql,qr);
107 return;
108 }
109 inline ll Ask(int x){
110 int fx&＃61;top[x];
111 Ans&＃61;0;
112 while(fx!&＃61;1){
113 Query(1,seg[fx],seg[x]);
114 x&＃61;fa[fx];
115 fx&＃61;top[x];
116 }
117 Query(1,1,seg[x]);
118 return Ans;
119 }
120 int main(){
121 N&＃61;rd();Q&＃61;rd();
122 for(int i&＃61;1;i<&＃61;N;i&＃43;&＃43;)W[i]&＃61;rd();
123 for(int i&＃61;1;i){
124 a&＃61;rd();b&＃61;rd();
125 Add_edge(a,b);
126 Add_edge(b,a);
127 }
128 Dfs1(1,0);
129 seg[0]&＃61;seg[1]&＃61;rev[1]&＃61;top[1]&＃61;1;
130 Dfs2(1);
131 Build(1,1,N);
132 while(Q--){
133 o&＃61;rd();
134 if(o&＃61;&＃61;1||o&＃61;&＃61;2){
135 X&＃61;rd();A&＃61;rd();
136 if(o&＃61;&＃61;1)Update(1,seg[X],seg[X],A);
137 else Update(1,seg[X],tu[X],A);
138 }
139 else{
140 X&＃61;rd();
141 printf("%lld\n",Ask(X));
142 }
143 }
144 return 0;
145 }